package com.lw.leetcode.stack.b;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 6080. 使数组按非递减顺序排列
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/30 9:15
 */
public class TotalSteps {

    public static void main(String[] args) {
        TotalSteps test = new TotalSteps();

        // 3
//        int[] arr = {5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11};

        // 6
//        int[] arr = {10, 1, 2, 3, 4, 5, 6, 1, 2, 3};

        // 2
//        int[] arr = {5, 11, 7, 8, 11};

        // 3
//        int[] arr = {7, 14, 4, 14, 13, 2, 6, 13};

        // 3
//        int[] arr = {14, 13, 2, 6, 13};

        // 10
//        int[] arr = {1851, 398, 907, 995, 1167, 1214, 1423, 1452, 1464, 1474, 1311, 1427, 1757};

        // 4
        int[] arr = {1851, 1452, 1464, 1474, 1311, 1427, 1757};

        int i = test.totalSteps(arr);
        System.out.println(i);
    }

    public int totalSteps(int[] nums) {
        int max = 0;
        int item = nums[0];
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> counts = new Stack<>();
        for (int num : nums) {
            if (num >= item) {
                item = num;
                while (!counts.isEmpty()) {
                    max = Math.max(max, counts.pop());
                }
                stack.clear();
                continue;
            }
            int c = 0;
            while (!stack.isEmpty() && stack.peek() <= num) {
                stack.pop();
                c = Math.max(c, counts.pop());
            }
            stack.add(num);
            counts.add(c + 1);
        }
        while (!counts.isEmpty()) {
            max = Math.max(max, counts.pop());
        }
        return max;
    }

}
